package _10_串;
/*
    字符串的KMP算法
 */
public class KMP {
    public static int indexOf(String text,String pattern){
        if(text == null || pattern == null) return -1;
        char[] textChars = text.toCharArray();
        int tLen = textChars.length; //文本串的长度
        if(tLen == 0) return -1;
        char[] patternChars = pattern.toCharArray();
        int pLen = patternChars.length; //模式串的长度
        if(pLen == 0) return -1;
        if(tLen < pLen) return -1; //文本串的长度小于模式串的长度

        //拿到模式串的next表
        int[] next = next(pattern);

        int pi = 0,ti = 0; // pi模式串的起点，ti文本串的起点
        int LinJieZhi = tLen - pLen; //tLen - pLen 文本串和模式串开始比较最后一次的临界值,
        //ti - pi 是每一轮比较中text首个比较字符的位置,减少比较次数
        while(pi<pLen && ti-pi<=LinJieZhi){
            //如果模式串在0位置失配，那么next[pi] = -1; <0,文本串向后移动一位，模式串去0位置，刚好满足if里
            if(pi<0 || textChars[ti] == patternChars[pi]){ //匹配成功，两个都向下跟进
                ti++;
                pi++;
            }else{ //失配的时候
                pi = next[pi];
            }
        }
        //只考虑pi == pLen的情况
        return (pi == pLen) ? (ti-pi) : -1;
    }

    /*
        生成模式串的next表,存放模式串的最大公共前缀和后缀
     */
    private static int[] next(String pattern){
        char[] chars = pattern.toCharArray();
        int[] next = new int[chars.length]; //next表的构造，存放模式串的前后最大公共前缀子串后缀
        next[0] = -1; //next表中的0号索引位-1
        // n == next[i] 也就是i索引字符前面的最大公共前缀和后缀的长度
        int n = -1; //初始值位-1
        int i= 0;
        int iMax = chars.length-1; //数组索引最大值
        while(i< iMax){
            //如果i索引的字符和n索引的字符相等
            // n<0是为了初始条件
            if(n<0 || chars[i] == chars[n]){
               next[++i] = ++n; //将i+1位置的字符的最大公共字串长度变为n的最大公共字串+1
            }else{ //失配的地方,缩小比较范围
                n = next[n]; //缩小范围进行比较
            }
        }
        return next;
    }

    public static void main(String[] args) {
        System.out.println(KMP.indexOf("Hello World","H"));
        System.out.println(KMP.indexOf("Hello World","d"));
        System.out.println(KMP.indexOf("Hello World","or"));
        System.out.println(KMP.indexOf("Hello World","abc"));
    }
}
